#!/usr/bin/env ruby
# -*- coding: us-ascii -*-

class String
  # From "Mastering Algorithms in C", p. 146, from the Dragon Book.
  # Remember to mod the return result by the Hash size (a prime).
  # The return value never exceeds 4 bytes, and I don't know how to 
  # adjust the literals to get to 8 bytes for JRuby without overflowing.
  def dragonhash
    val = 0
    each_byte do |ascii_value|
      val = (val << 4) + ascii_value
      tmp = val & 0xf0000000
      unless tmp.zero?
        val = val ^ (tmp >> 24)
        val = val ^ tmp
      end
    end
    return val
  end
  
  def rabinkarp
    # See "Mastering Algos with Perl" p. 362ff
    raise NotImplementedError, 'Eliz still needs to do this'
  end
end

########################################

if $0 == __FILE__
  getty = 'four score and seven years ago our fathers brought forth'
  strings = getty.split << getty << getty*(rand(100)+1)
  strings.each do |s|
    dragon = s.dragonhash
    raise "#{s.inspect}.dragonhash is too big!" if dragon.size > 1.size
    puts "#{s.inspect}: #{dragon} (#{dragon.size} bytes)"
  end
end
